{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "line_segmentation.ipynb",
      "provenance": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {
        "id": "X6VjSPyDguD-"
      },
      "outputs": [],
      "source": [
        "#All important library imports go here\n",
        "import os\n",
        "import numpy as np\n",
        "import cv2\n",
        "from scipy.signal import find_peaks, peak_prominences\n",
        "import matplotlib.pyplot as plt\n",
        "from google.colab.patches import cv2_imshow\n",
        "from IPython.display import clear_output\n",
        "from google.colab import files\n",
        "\n",
        "%matplotlib inline  \n",
        "# if you are running this code in Jupyter notebook"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "#Unzipping the folder which contains the paragraph images to be segmented\n",
        "#In this case, the zipped folder is uploaded to google colab in the default directory Content\n",
        "#The zipped file name is files.zip\n",
        "!unzip \"/content/files.zip\" -d \"/content/\"\n",
        "\n",
        "#clearing the console after unzipping\n",
        "clear_output()"
      ],
      "metadata": {
        "id": "oEi7lLJthSj-"
      },
      "execution_count": 3,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# getting the names of all the paragraph images in the directory files\n",
        "filenames=os.listdir('/content/files')\n",
        "#stripping the extension of the image file from the string of the filename for further use\n",
        "#Note that KHATT dataset provides the images with .tif extension\n",
        "filenames_split=[filename.replace('.tif', '') for filename in filenames]"
      ],
      "metadata": {
        "id": "XG0Tep48hvge"
      },
      "execution_count": 4,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def directionalHistogram(img, direction='H'):\n",
        "  # a function which outputs the intensity histogram for a given image along \n",
        "  #x or y directions\n",
        "\n",
        "    (w,h) = img.shape\n",
        "    sum = []\n",
        "    pixel_count=0\n",
        "\n",
        "    if(direction=='H'):\n",
        "        for j in range(w-1):\n",
        "          for i in range(h-1):\n",
        "            pixel=img[j,i]\n",
        "            if(pixel==255):\n",
        "              pixel_count+=1\n",
        "          sum.append(pixel_count)\n",
        "          pixel_count=0\n",
        "\n",
        "    else:\n",
        "       for j in range(h-1):\n",
        "          for i in range(w-1):\n",
        "            pixel=img[i,j]\n",
        "            if(pixel==255):\n",
        "              pixel_count+=1\n",
        "          sum.append(pixel_count)\n",
        "          pixel_count=0\n",
        "\n",
        "    return sum\n",
        "\n",
        "##############################################################\n",
        "\n",
        "def smoothHist(hist,kernel_size):\n",
        "  # A function to smooth out the noise in intensity histograms of an image\n",
        "  kernel = np.ones(kernel_size) / kernel_size\n",
        "  return np.convolve(hist, kernel, mode='same')\n",
        "\n",
        "##############################################################\n",
        "\n",
        "def thresholding(image, threshold, typee='Binary', param1=0, param2=0):\n",
        "  # A function to apply intensity thresholding to a grey-scale image\n",
        "  # The thresholding could be simple binary thresholding or adaptive gaussian thresholding\n",
        "  # If the type is not set to 'Binary' then the parameters for adaptive thresholdinf must\n",
        "  # be used which are:\n",
        "  #param1: local region size ( preferably an odd number)\n",
        "  #param2: constant to be added to local mean\n",
        "  if(typee.lower()=='binary'):\n",
        "    ret, thresh= cv2.threshold(image,threshold,255,cv2.THRESH_BINARY_INV)\n",
        "  else:\n",
        "    thresh = cv2.adaptiveThreshold(image,255,cv2.ADAPTIVE_THRESH_GAUSSIAN_C, cv2.THRESH_BINARY_INV,param1,param2)\n",
        "  return thresh\n",
        "\n",
        "##############################################################\n",
        "\n",
        "def peakinterp(interp_factor, hist, prominence_factor):\n",
        "  #Given an intensity histogram of an image, this function increases the resolution of the histogram\n",
        "  #by interpolation and then finds the sharp peaks in this histogram using find_peaks()\n",
        "  #Interp factor controls the new resolution of the histogram\n",
        "  #Prominence factor decides how much the targeted peaks stand out from the baseline of the spectrum\n",
        "  resampled_pixel_space=np.linspace(0, interp_factor*len(hist)-1,interp_factor*len(hist))*(1/interp_factor)\n",
        "  Original_pixel_space=np.linspace(0, len(hist)-1, len(hist))\n",
        "  hist_interp = np.interp(resampled_pixel_space, Original_pixel_space, hist)\n",
        "  peaks, properties = find_peaks(hist_interp, prominence=np.max(hist_interp)/prominence_factor, width=50)\n",
        "\n",
        "  return(peaks,hist_interp, resampled_pixel_space, Original_pixel_space)\n",
        "\n",
        "  ##############################################################\n",
        "\n",
        "def findGradSignChange(hist_interp, resampled_pixel_space, Original_pixel_space):\n",
        "    #Given an interpolated intensity histogram, this function finds the 1st derivative\n",
        "    # of this histogram and outputs a vector of ones and zeros determining the sign\n",
        "    # of the calculated derivative.\n",
        "    # When the sign is +ve, the vector has 1\n",
        "    # When the sign is -ve, the vector has 0\n",
        "    hist_grad=np.gradient(hist_horizontal_smooth_interp)\n",
        "    hist_grad_sign_change=np.where(hist_grad >= 0, 1, 0)\n",
        "    return hist_grad_sign_change\n",
        "\n",
        "   ##############################################################\n",
        "\n",
        "def rle(ia):\n",
        "\n",
        "        #A function which when given a sequence of binary values outputs the following:\n",
        "        # 1) the start positions of a portion of repeated values in the sequence\n",
        "        # 2) the length of the portion of repeated values\n",
        "        #This will be useful in dealing with the vector representing the sign change of\n",
        "        #1st derivative of image intensity histogram\n",
        "       \n",
        "\n",
        "        n = len(ia)\n",
        "        if n == 0: \n",
        "            return (None, None, None)\n",
        "        else:\n",
        "            y = ia[1:] != ia[:-1]               # pairwise unequal (string safe)\n",
        "            i = np.append(np.where(y), n - 1)   # must include last element posi\n",
        "            z = np.diff(np.append(-1, i))       # run lengths\n",
        "            p = np.cumsum(np.append(0, z))[:-1] # positions\n",
        "            return(z, p, ia[i])\n",
        " ##############################################################\n",
        "\n",
        "def cutPositions(runlengths, startpositions, values, threshold,interp_factor):\n",
        "  #Give a vector of ones and zeroes representing the sign change of 1st deriv. of\n",
        "  # a histogram, this function smoothes out the abrupt changes in gradient sign\n",
        "  # which might be an artifact of the gradient calculation.\n",
        "\n",
        "  # This function also gives an estimation of the possible cutting locations to\n",
        "  # extract lines\n",
        "\n",
        "  viable_index=0\n",
        "  for i in range(len(runlengths)):\n",
        "    current_length=runlengths[i]\n",
        "    if(current_length<threshold):\n",
        "      values[i]=values[viable_index]\n",
        "    viable_index=i\n",
        "\n",
        "  new_hist=[]\n",
        "  for i in range(len(startpositions)):\n",
        "    if(values[i]):\n",
        "      new_hist+=np.ones(runlengths[i]-1).tolist()\n",
        "    else:\n",
        "      new_hist+=np.zeros(runlengths[i]-1).tolist()\n",
        "\n",
        "  cutpos=[]\n",
        "  for i in range(1,len(startpositions)):\n",
        "    last=values[i-1]\n",
        "    current=values[i]\n",
        "    if((last==0 and current==1)):\n",
        "      cutpos.append(startpositions[i])\n",
        "    elif((last==1 and i==1)):\n",
        "      cutpos.append(0)\n",
        "\n",
        "\n",
        "  return (cutpos, new_hist)\n",
        "\n",
        "######################################################\n",
        "def optimalThreshold(cutpos, runlengths, startpositions, values, new_hist, peaks, init_threshold, interp_factor):\n",
        "\n",
        "  #when removing noise from the gradient sign vector prior to determining the cut locations, we use a threshold\n",
        "  #value on the run lengths of ones and zeros.\n",
        "  #An optimal value of the threshold is the value which when used gives us as many cut locations as detected peaks\n",
        "  # in the original histogram\n",
        "  while((len(cutpos)!= len(peaks))):\n",
        "      init_threshold=init_threshold+interp_factor\n",
        "      (cutpos, new_hist)=cutPositions(runlengths, startpositions, values, init_threshold,interp_factor)\n",
        "\n",
        "  (cutpos, new_hist)=cutPositions(runlengths, startpositions, values, np.abs(init_threshold-interp_factor),interp_factor)\n",
        "  cutpos=np.array(cutpos)/interp_factor\n",
        "  \n",
        "  return (cutpos, new_hist)\n",
        "\n",
        "###################################################\n",
        "\n",
        "def cropImageToLines(cutpos, image, direction='H'):\n",
        "  (w,h)=image.shape\n",
        "  cropped_images=[]\n",
        "  if(direction=='H'):\n",
        "    for i in range(len(cutpos)):\n",
        "      currentpos=cutpos[i]\n",
        "      lastpos=cutpos[i-1]\n",
        "      cropped_images.append(image[lastpos:currentpos-1,0:h-1])\n",
        "  else:\n",
        "    for i in range(len(cutpos)):\n",
        "      currentpos=cutpos[i]\n",
        "      lastpos=cutpos[i-1]\n",
        "      cropped_images.append(image[0:w-1, lastpos:currentpos-1])\n",
        "\n",
        "  return cropped_images"
      ],
      "metadata": {
        "id": "GK_EdEYDiJsX"
      },
      "execution_count": 7,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#create the directory that will hold your line images\n",
        "!mkdir files_segmented\n",
        "\n",
        "#loop over all prargraph images\n",
        "for m in range(len(filenames)):\n",
        "\n",
        "    #Read the paragraph image and apply thresholding\n",
        "    image = cv2.imread('/content/files/'+filenames[m],0)\n",
        "    (w,h) = image.shape\n",
        "    thresh1=thresholding(image, 240, typee='Binary', param1=0, param2=0)\n",
        " \n",
        "\n",
        "    #obtaining horizontal histogram and smoothing it\n",
        "    hist_horizontal=directionalHistogram(thresh1)\n",
        "    hist_horizontal_smooth=smoothHist(hist_horizontal,17)\n",
        "\n",
        "    #Obtaining peak locations from the smoothed horizontal histogram\n",
        "    init_threshold=50\n",
        "    interp_factor=100\n",
        "    (peaks,hist_horizontal_smooth_interp,resampled_pixel_space, Original_pixel_space)=peakinterp(interp_factor, hist_horizontal_smooth, 8)\n",
        "    hist_grad_sign_change=findGradSignChange(hist_horizontal_smooth_interp, resampled_pixel_space, Original_pixel_space)\n",
        "\n",
        "    #obtaining the piecewise constant function approximating the sign change behavior of the 1st derivative of the horizontal histogram\n",
        "    runlengths, startpositions, values =rle(hist_grad_sign_change)\n",
        "    (cutpos, new_hist)=cutPositions(runlengths, startpositions, values, init_threshold, interp_factor)\n",
        "\n",
        "\n",
        "    #Removing undesired sign changes from the piecewise function which are the result of noise or numerical artifiacts, not the desired peaks\n",
        "    cutpos, new_hist=optimalThreshold(cutpos, runlengths, startpositions, values, new_hist, peaks, 50, 100)\n",
        "    #displaying lines extracted from the image\n",
        "    lines= cropImageToLines(cutpos.astype(int), thresh1)\n",
        "    for i in range(len(lines)):\n",
        "        cv2.imwrite(\"/content/files_segmented/\"+filenames_split[m]+\"_\"+str(i)+\".tif\", lines[i])\n",
        "\n",
        "\n",
        "#downloading the line image directory in zipped format\n",
        "!zip -r /content/files_segmented.zip /content/files_segmented\n",
        "files.download(\"/content/files_segmented.zip\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 721
        },
        "id": "34Dz-4eFjPwe",
        "outputId": "1224b5e6-0fd7-4339-9d82-243dad027c87"
      },
      "execution_count": 9,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "mkdir: cannot create directory ‘files_segmented’: File exists\n",
            "  adding: content/files_segmented/ (stored 0%)\n",
            "  adding: content/files_segmented/AHTD3A0161_Para1_4.tif (deflated 35%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_2.tif (deflated 25%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_2.tif (deflated 13%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_3.tif (deflated 27%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para1_3.tif (deflated 23%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_3.tif (deflated 11%)\n",
            "  adding: content/files_segmented/AHTD3A0161_Para1_1.tif (deflated 17%)\n",
            "  adding: content/files_segmented/AHTD3A0151_Para4_0.tif (deflated 89%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para1_0.tif (deflated 43%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_0.tif (deflated 96%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_5.tif (deflated 35%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_1.tif (deflated 13%)\n",
            "  adding: content/files_segmented/AHTD3A0161_Para1_0.tif (deflated 86%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para4_1.tif (deflated 26%)\n",
            "  adding: content/files_segmented/AHTD3A0161_Para1_3.tif (deflated 22%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_1.tif (deflated 27%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_6.tif (deflated 44%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_5.tif (deflated 16%)\n",
            "  adding: content/files_segmented/AHTD3A0151_Para4_4.tif (deflated 17%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_4.tif (deflated 23%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_4.tif (deflated 21%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_3.tif (deflated 22%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para1_2.tif (deflated 34%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_5.tif (deflated 19%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para1_1.tif (deflated 14%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_0.tif (deflated 71%)\n",
            "  adding: content/files_segmented/AHTD3A0151_Para4_1.tif (deflated 15%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para4_2.tif (deflated 25%)\n",
            "  adding: content/files_segmented/AHTD3A0158_Para1_4.tif (deflated 18%)\n",
            "  adding: content/files_segmented/AHTD3A0151_Para4_3.tif (deflated 10%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para4_3.tif (deflated 22%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_0.tif (deflated 41%)\n",
            "  adding: content/files_segmented/AHTD3A0151_Para4_2.tif (deflated 20%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para4_4.tif (deflated 32%)\n",
            "  adding: content/files_segmented/AHTD3A0161_Para1_2.tif (deflated 21%)\n",
            "  adding: content/files_segmented/AHTD3A0144_Para4_1.tif (deflated 39%)\n",
            "  adding: content/files_segmented/AHTD3A0152_Para4_2.tif (deflated 26%)\n",
            "  adding: content/files_segmented/AHTD3A0168_Para4_0.tif (deflated 88%)\n"
          ]
        },
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ],
            "application/javascript": [
              "\n",
              "    async function download(id, filename, size) {\n",
              "      if (!google.colab.kernel.accessAllowed) {\n",
              "        return;\n",
              "      }\n",
              "      const div = document.createElement('div');\n",
              "      const label = document.createElement('label');\n",
              "      label.textContent = `Downloading \"${filename}\": `;\n",
              "      div.appendChild(label);\n",
              "      const progress = document.createElement('progress');\n",
              "      progress.max = size;\n",
              "      div.appendChild(progress);\n",
              "      document.body.appendChild(div);\n",
              "\n",
              "      const buffers = [];\n",
              "      let downloaded = 0;\n",
              "\n",
              "      const channel = await google.colab.kernel.comms.open(id);\n",
              "      // Send a message to notify the kernel that we're ready.\n",
              "      channel.send({})\n",
              "\n",
              "      for await (const message of channel.messages) {\n",
              "        // Send a message to notify the kernel that we're ready.\n",
              "        channel.send({})\n",
              "        if (message.buffers) {\n",
              "          for (const buffer of message.buffers) {\n",
              "            buffers.push(buffer);\n",
              "            downloaded += buffer.byteLength;\n",
              "            progress.value = downloaded;\n",
              "          }\n",
              "        }\n",
              "      }\n",
              "      const blob = new Blob(buffers, {type: 'application/binary'});\n",
              "      const a = document.createElement('a');\n",
              "      a.href = window.URL.createObjectURL(blob);\n",
              "      a.download = filename;\n",
              "      div.appendChild(a);\n",
              "      a.click();\n",
              "      div.remove();\n",
              "    }\n",
              "  "
            ]
          },
          "metadata": {}
        },
        {
          "output_type": "display_data",
          "data": {
            "text/plain": [
              "<IPython.core.display.Javascript object>"
            ],
            "application/javascript": [
              "download(\"download_fd835c13-7362-41f4-97b7-9342ab855505\", \"files_segmented.zip\", 343095)"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}